package com.wc.AlgoOJ_train.train2_DP训练.c3.DP0104;

import java.util.Scanner;

/**
 * @Author congge
 * @Date 2024/1/12 22:26
 * @description
 * 多重背包2 二进制优化
 */
public class Answer {
    static int maxN = 2000 + 7;
    static int[] dp = new int[maxN];
    static int n, m;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        m = sc.nextInt();
        for (int i = 1; i <= n; i++) {
            int w, v, l;
            w = sc.nextInt();
            v = sc.nextInt();
            l = sc.nextInt();
            // 二进制取个数，先取个数为准，别的都可以用这几个二级制来表示
            for (int k = 1; l > 0; k <<= 1) {
                // 当最后一个不够的时候，就取最后剩下的数
                if (l < k) k = l;
                l -= k;
                // 当前个数用01背包解答
                for (int j = m; j >= k * w; j--) {
                    dp[j] = Math.max(dp[j], dp[j - k * w] + k * v);
                }
            }
        }
        System.out.println(dp[m]);
    }
}
